class TrieNode:
    def __init__(self, value=' '):
        self.children = {}
        self.is_end_of_word = False
        self._value = value

    def has_child(self, c):
        return c in self.children


class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        current = self.root
        for c in word:
            if not current.has_child(c):
                current.children[c] = TrieNode(c)
            current = current.children[c]
        if current.is_end_of_word:
            return False
        current.is_end_of_word = True
        return True

    def auto_suggest(self, prefix):
        if not prefix:
            return []
            
        current_node = self.root
        for c in prefix:
            if not current_node.has_child(c):
                return []
            current_node = current_node.children[c]
        return sorted(self.get_all_words_with_prefix(current_node, prefix))

    def get_all_words_with_prefix(self, root, prefix):
        words = []
        if root is None:
            return words
        
        if root.is_end_of_word:
            words.append(prefix)
            
        for char, child in root.children.items():
            words.extend(self.get_all_words_with_prefix(child, prefix + char))
            
        return words

    def get_all_words(self):
        return self.get_all_words_with_prefix(self.root, "")

    def print_trie_structure(self):
        print("\nroot")
        self._print_trie_nodes(self.root)

    def _print_trie_nodes(self, root, format=" ", is_last_child=True):
        if root is None:
            return

        print(f"{format}", end='')

        if is_last_child:
            print("└─", end='')
            format += "  "
        else:
            print("├─", end='')
            format += "│ "

        print(f"{root._value}")

        child_count = len(root.children)
        i = 0
        children = sorted(root.children.items())

        for key, child in children:
            i += 1
            is_last = i == child_count
            self._print_trie_nodes(child, format, is_last)

    def get_spelling_suggestions(self, word):
        if not word:
            return []
            
        first_letter = word[0]
        if first_letter not in self.root.children:
            return []
            
        suggestions = []
        words = self.get_all_words_with_prefix(self.root.children[first_letter], first_letter)

        for w in words:
            distance = self.levenshtein_distance(word, w)
            if distance <= 2:
                suggestions.append(w)

        return suggestions

    def levenshtein_distance(self, s, t):
        if not s: return len(t)
        if not t: return len(s)
        
        m = len(s)
        n = len(t)
        
        # Create a matrix of size (m+1) x (n+1)
        d = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
        
        # Initialize first row and column
        for i in range(m + 1):
            d[i][0] = i
        for j in range(n + 1):
            d[0][j] = j
            
        # Fill in the rest of the matrix
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if s[i-1] == t[j-1]:
                    cost = 0
                else:
                    cost = 1
                d[i][j] = min(d[i-1][j] + 1,      # deletion
                            d[i][j-1] + 1,      # insertion
                            d[i-1][j-1] + cost) # substitution
                            
        return d[m][n]

    def search(self, word):
        current = self.root
        for c in word:
            if not current.has_child(c):
                return False
            current = current.children[c]
        return current.is_end_of_word

    def delete(self, word):
        def _delete_helper(node, word, depth=0):
            if depth == len(word):
                if node.is_end_of_word:
                    node.is_end_of_word = False
                return len(node.children) == 0

            char = word[depth]
            if char not in node.children:
                return False

            should_delete_node = _delete_helper(node.children[char], word, depth + 1)

            if should_delete_node:
                del node.children[char]
                return len(node.children) == 0

            return False

        if not word:
            return False

        _delete_helper(self.root, word)
        return True